// 定义单链表节点类
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}

class Solution {
    // 查找两个链表的相交节点
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode opA = headA, opB = headB;
        // 同步遍历两个链表，使指针到达链表末尾
        while (opA != null && opB != null) {
            opA = opA.next;
            opB = opB.next;
        }
        int cnt = 0;
        // 计算链表 A 比链表 B 多的节点数
        while (opA != null) {
            cnt++;
            opA = opA.next;
        }
        // 计算链表 B 比链表 A 多的节点数
        while (opB != null) {
            cnt--;
            opB = opB.next;
        }
        // 让较长链表的指针先移动多余的节点数
        if (cnt > 0) {
            while (cnt-- > 0) headA = headA.next;
        } else {
            while (cnt++ < 0) headB = headB.next;
        }
        // 同步遍历两个链表，直到找到相交节点
        while (headA != headB) {
            headA = headA.next;
            headB = headB.next;
        }
        return headA;
    }

    public static void main(String[] args) {
        // 创建链表 A: 1 -> 2 -> 3 -> 6 -> 7
        ListNode headA = new ListNode(1);
        headA.next = new ListNode(2);
        headA.next.next = new ListNode(3);
        ListNode commonNode = new ListNode(6);
        headA.next.next.next = commonNode;
        commonNode.next = new ListNode(7);

        // 创建链表 B: 4 -> 5 -> 6 -> 7
        ListNode headB = new ListNode(4);
        headB.next = new ListNode(5);
        headB.next.next = commonNode;

        Solution solution = new Solution();
        ListNode intersectionNode = solution.getIntersectionNode(headA, headB);
        if (intersectionNode != null) {
            System.out.println("相交节点的值是: " + intersectionNode.val);
        } else {
            System.out.println("两个链表没有相交节点。");
        }
    }
}
